(*･∀-)b
嗨，我是wec，今天是DAY 25。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定兩個整數n和k，返回從1到n中選擇k個數字的所有組合。

🔎 解題思路＆程式碼

1️⃣ 回溯法

第1步： 建立一個空的列表 result 用來儲存所有組合。
第2步： 定義下列參數：
start：從哪個數字開始選擇。
path：當前選擇的數字列表。
n和k：給定的範圍和要選擇的數字個數。
result：最終的結果列表。
第3步： 如果path的長度達到k，將其加入result。
第4步： 從start開始，遍歷到n的數字。將當前數字i加入path，然後調用backtrack繼續選擇下一個數字（i + 1）。回溯（就是撤回）當前的選擇，嘗試其他可能性。
第5步： 初次調用backtrack，從1開始選擇。
程式碼：

def combine(n, k)
  result = [] 

  def backtrack(start, path, n, k, result)
    if path.size == k
      result << path.dup
      return
    end

    (start..n).each do |i|
      path << i 
      backtrack(i + 1, path, n, k, result) 
      path.pop 
    end
  end

  backtrack(1, [], n, k, result) 
  result
end

🔎 總結

時間複雜度

回溯法： O(C(n, k))，代表從n個元素中選擇k個元素的組合數(為指數級別)。
➡️ 為甚麼叫他經一事長一智的方法就是因為回溯法就是一個不斷在嘗試很多不同種方法的演算法，透過不斷的回溯、撤回來尋找不同的可能性與組合，簡直比我查成績的那瞬間還有勇氣。不過因為它可以撤回的這種特性，所以才可以有效的解決問題(σ´∀`)σ !

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃蘋果。
明天要說：Ruby精選刷題！Medium路跑D-18(>∀･)⌒☆